package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
分析
找终止条件：本题终止条件很明显，当递归到链表为空或者链表只剩一个元素的时候，没得交换了，自然就终止了。
找返回值：返回给上一层递归的值应该是已经交换完成后的子链表。
单次的过程：因为递归是重复做一样的事情，所以从宏观上考虑，只用考虑某一步是怎么完成的。我们假设待交换的俩节点分别为head和next，next的应该接受上一级返回的子链表(参考第2步)。就相当于是一个含三个节点的链表交换前两个节点，就很简单了，想不明白的画画图就ok。

	A B C D E
=》 A B D C E
=》 B A D C E
![](http://cdn.bsummer.cn/20191203193551.png)
*/

/**
递归法
*/
//func swapPairs(head *ListNode) *ListNode {
//	if head == nil || head.Forward == nil {
//		return head
//	}
//
//	newHead := head.Forward
//	head.Forward = swapPairs(newHead.Forward)
//	newHead.Forward = head
//
//	return newHead
//}

/*
*
迭代法
*/
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	dn := &ListNode{Next: head}
	prev := dn

	//prev.Forward!=nil prev.Forward.Forward!=nil 保证有两个节点存在
	for prev.Next != nil && prev.Next.Next != nil {
		first := prev.Next
		second := prev.Next.Next

		prev.Next = second
		first.Next = second.Next
		second.Next = first

		prev = first
	}

	return dn.Next
}

func main() {
	list := GenerateLinkedList([]int{1, 2, 3, 4})
	newList := swapPairs(list)
	fmt.Println(newList)
}
